/**
 * 希尔排序
 * @author dc
 * @Classname Sell
 * @Date 2020/1/3 20:11
 */
public class Shell extends BaseSort{
    /**
     * 实现希尔排序,将a数组升序排列
     * @param a
     */
     public static void sort(Comparable[] a) {
         int N=a.length;
         int h=1;
         while (h<N/3){
             h=3*h+1;
         }
         while(h>=1){
             //将数组变为h有序,即每段h内的值都是有序的
             for(int i=h;i<N;i++){
                 //将a[i]插入a[i-h],a[i-2*h]...中
                 //将数组分为几段,每段对应的第几位数进行比较排序
                 for(int j=i;j>=h&&less(a[j],a[j-h]);j-=h){
                     exch(a,j,j-h);
                 }
             }
             h=h/3;
         }
      }

}
